package com.hanxiaozhang.link.singlylink;

import com.hanxiaozhang.util.AlgorithmUtil;

/**
 * 〈一句话功能简述〉<br>
 * 〈单链表〉
 *
 * @author hanxinghua
 * @create 2021/9/5
 * @since 1.0.0
 */
public class SinglyLink {

    public static void main(String[] args) {

        System.out.println("-----基本使用-----");
        // # 空链表
        Node head = null;
        // # 插入
        // -- 头为空节点插入
        head = addByNullHead(head, 2);
        // -- 头节点插入
        head = addByHead(head, 3);
        // -- 中间节点插入(插入在 head 与 next 之间)
        head = addByMiddle(head, 1);
        head = addByMiddle(head, 4);
        // # 循环
        whileNode(head);
        // # 删除
        // -- 头结点删除
//        head = removeByHead(head);
//        whileNode(head);
        // -- 中间结点删除(删除在 head 与 next 之间)
        head = removeByMiddle(head);
        whileNode(head);

        // 翻转
//        Node head = AlgorithmUtil.generateRandomSinglyLinked(4, 10);
//        whileNode(head);
//        head = reverse(head);
//        whileNode(head);

//        Node head = AlgorithmUtil.generateRandomSinglyLinked(20, 10);
//        whileNode(head);
//        head = topic1(head, 3);
//        whileNode(head);


    }


    /**
     * 头为空节点插入
     *
     * @param head
     * @param data
     * @return
     */
    public static Node addByNullHead(Node head, Integer data) {
        head = new Node(data, null);
        return head;
    }

    /**
     * 头节点插入
     *
     * @param head
     * @param data
     * @return
     */
    public static Node addByHead(Node head, Integer data) {
        Node node = new Node(data, null);
        head.next = node;
        return head;
    }

    /**
     * 中间节点插入
     * 插入在 head 与 next 之间
     *
     * @param head
     * @param data
     * @return
     */
    public static Node addByMiddle(Node head, Integer data) {
        // 注意先后顺序：
        // 首先，node后继节点指向head后继节点
        Node node = new Node(data, head.next);
        // 然后，head后继节点指向node
        head.next = node;
        return head;
    }

    /**
     * 循环打印
     *
     * @param head
     */
    public static void whileNode(Node head) {
        System.out.println("----------");
        while (head != null) {
            System.out.println(head.data);
            head = head.next;
        }
    }

    /**
     * 头结点删除
     */
    public static Node removeByHead(Node head) {
        head = head.next;
        return head;
    }

    /**
     * 中间节点删除
     * 删除在 head 与 next 之间
     *
     * @param head
     * @return
     */
    public static Node removeByMiddle(Node head) {
        head.next = head.next.next;
        return head;
    }


    /**
     * 思路是，从head的后继节点开始，把指针指向前继
     * <p>
     * head 循环条件
     * pre 记录前继节点
     *
     * @param head
     * @return
     */
    public static Node reverse(Node head) {
        // 前继节点
        Node pre = null;
        // 后继节点
        Node next = null;
        while (head != null) {
            // 获取当前节点的后继节点
            next = head.next;
            // 当前节点的后继节点，指向前继节点
            head.next = pre;
            // pre 移动到一个位置
            pre = head;
            // head 移动到一个位置
            head = next;
        }
        return pre;
    }


    /**
     * 从链表中，删除某个元素
     * 声明两个变量 前继节点和当前节点
     *
     * @param head
     * @param target
     * @return
     */
    private static Node topic1(Node head, int target) {
        if (head == null) {
            return null;
        }
        // 去除头结点是目标数情况
        while (head.next != null) {
            if ((int) head.data != target) {
                break;
            }
            head = head.next;
        }
        // 前继节点
        Node pre = head;
        // 当前节点
        Node cur = head;
        while (cur != null) {
            if ((int) cur.data == target) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

}
